package main

import "fmt"

func main() {
	fmt.Println(longestValidParentheses("()((()()))()"))
}

//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
//
//
//
//
//
// 示例 1：
//
//
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
//
//
// 示例 2：
//
//
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
//
//
// 示例 3：
//
//
//输入：s = ""
//输出：0
//
//
//
//
// 提示：
//
//
// 0 <= s.length <= 3 * 10⁴
// s[i] 为 '(' 或 ')'
//
//
//
// Related Topics 栈 字符串 动态规划 👍 1674 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
func longestValidParentheses(s string) (ans int) {
	// 先确定子串的左边界
	// 然后想办法确定右边界
	// 遇到(，加一
	// 遇到)，减一
	// 如果为正数，继续往后找右边界
	// 如果为0，则将当前子串长度记录，与之前记录的结果做比较取大的那个，继续往后找右边界
	// 如果为负数，那就不可能再形成有效子串了，结束
	// 右移左边界，重复上述步骤
	for i := 0; i < len(s); i++ {
		tmp := 0
		for j := i; j < len(s); j++ {
			if s[j] == '(' {
				tmp++
			} else {
				tmp--
			}
			if tmp == 0 {
				if j-i+1 > ans {
					ans = j - i + 1
				}
			} else if tmp < 0 {
				break
			}
		}
	}
	return ans
}

//leetcode submit region end(Prohibit modification and deletion)
